package com.fengdi.everyday.middle;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Description 3346 执行操作后元素的最高频率
 * @Date 09:16
 */
public class MaxFrequency {

    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);

        int ans = 0;
        Map<Integer, Integer> numCount = new HashMap<>();

        int lastIndex = 0;

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != nums[lastIndex]) { // 统计前面相同的值
                numCount.put(nums[lastIndex], i - lastIndex);
                ans = Math.max(ans, i - lastIndex);
                lastIndex = i;
            }
        }

        numCount.put(nums[lastIndex], nums.length - lastIndex);
        ans = Math.max(ans, nums.length - lastIndex);

        for(int i = nums[0]; i <= nums[nums.length - 1]; i++) {
            int l = this.leftBound(nums, i - k);
            int r = this.rightBound(nums, i + k);
            int tempAns = 0;
            if(numCount.containsKey(i)) {
                tempAns = Math.min(r - l + 1, numCount.get(i) + numOperations);
            }else {
                tempAns = Math.min(r - l + 1, numOperations);
            }
            ans = Math.max(tempAns, ans);
        }

        return ans;
    }


    private int leftBound(int[] nums, int value) { // 找到左边界
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < value) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }

    private int rightBound(int[] nums, int value) {// 找到右边界
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if(nums[mid] > value) {
                right = mid - 1;
            }else {
                left = mid;
            }
        }
        return left;
    }
}
